package leetcode_1000;

import java.util.Arrays;

/**
 *@author 周杨
 *SquaresOfASortedArray_977 给一个有序数组 返回里面每个数组都平方后的有序数组
 *describe: 双指针 空间换时间
 *2019年3月4日 上午9:46:48
 */
public class SquaresOfASortedArray_977 {
	//排序 时间复杂度O(nlogn) 空间复杂度O(1)
	public int[] sortedSquares(int[] A) {
        for(int i = 0;i < A.length;++i) {
        	A[i] = A[i]*A[i];
        }
        Arrays.sort(A);
        return A;
    }
	
	//双指针 用空间换时间 时间复杂度O(n) 空间复杂度O(n)
	public int[] sortedSquares1(int[] A) {
		int []res = new int[A.length];
        int left = 0,right = A.length-1;
        int i = A.length-1;
        while(left<=right) {
        	if(A[left]*A[left]<A[right]*A[right]) {
        		res[i--] = A[right]*A[right];
        		--right;
        	}else {
        		res[i--] = A[left]*A[left];
        		++left;
        	}
        }
        return res;
    }
}
